#include <stdio.h>
#include <memory.h>

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        int n, i, in;
        char data[ 5 ];
        scanf("%d", &n);
        scanf("%s", data);
        if ( data[ 2 ] == 'F' )
        {
            int queue[ n ], head = 0, tail = 0;
            for ( i = 0; i < n; i++ )
            {
                scanf("%s", data);
                if ( data[ 0 ] == 'I') 
                {
                    scanf("%d", &in);
                    queue[ tail ] = in;
                    tail++;
                }
                if ( data[ 0 ] == 'O' )
                {
                    if ( head < tail )
                    {
                        printf("%d\n", queue[ head ]);
                        head++;
                    }
                    else
                        printf("None\n");
                }
            }
        }
        else
        {
            int stack[ n + 1 ], head = 0;
            for ( i = 0; i < n; i++ )
            {
                scanf("%s", data);
                if ( data[ 0 ] == 'I') 
                {
                    scanf("%d", &in);
                    stack[ head ] = in;
                    head++;
                }
                if ( data[ 0 ] == 'O' )
                {
                    if ( head > 0 )
                    {
                        head--;
                        printf("%d\n", stack[ head ]);
                    }
                    else
                        printf("None\n");
                }
            }    
        }
    }
    return 0;
}
